~ chicken-core (master) /manual/Module (scheme lazy)

  1[[tags: manual]]
  2[[toc:]]
  3
  4== Module (scheme lazy)
  5
  6
  7Delayed evaluation
  8
  9<macro>(delay <expression>)</macro>
 10
 11Semantics: The delay construct is used together with the procedure force to
 12implement lazy evaluation or call by need. {{(delay <expression>)}} returns an
 13object called a promise which at some point in the future can be asked (by the 
 14force procedure) to evaluate <expression>, and deliver the resulting value. The
 15effect of <expression> returning multiple values is unspecified.
 16
 17<macro>(delay-force <expression>)</macro>
 18
 19Semantics: The expression {{(delay-force expression)}} is conceptually similar to
 20{{(delay (force expression))}}, with the difference that forcing the result of delay-force will
 21in effect result in a tail call to {{(force expression)}}, while forcing the result of 
 22{{(delay (force expression))}} might not. Thus iterative lazy algorithms that might result in a
 23long series of chains of delay and force can be rewritten using delay-force to
 24prevent consuming unbounded space during evaluation.
 25
 26<macro>(force promise)</macro>
 27
 28The force procedure forces the value of a
 29promise created by delay, delay-force, or make-promise.If no value has been
 30computed for the promise, then a value is computed and returned. The value of
 31the promise must be cached (or "memoized") so that if it is forced a second
 32time, the previously computed value is returned. Consequently, a delayed
 33expression is evaluated using the parameter values and exception handler of the
 34call to force which first requested its value. If
 35promise is not a promise, it may be returned unchanged.
 36
 37 (force (delay (+ 1 2)))    ==> 3
 38 (let ((p (delay (+ 1 2))))
 39   (list (force p) (force p))) ==>  (3 3)
 40
 41 (define integers
 42   (letrec ((next
 43             (lambda (n)
 44               (delay (cons n (next (+ n 1)))))))
 45     (next 0)))
 46 (define head
 47   (lambda (stream) (car (force stream))))
 48 (define tail
 49   (lambda (stream) (cdr (force stream))))
 50 
 51 (head (tail (tail integers))) ==>  2 
 52
 53The following example is a mechanical
 54transformation of a lazy stream-filtering algorithm into Scheme. Each call to a
 55constructor is wrapped in delay, and each argument passed to a deconstructor is
 56wrapped in force. The use of {{(delay-force ...)}} instead of {{(delay (force ...))}}
 57around the body of the procedure ensures that an ever-growing sequence of
 58pending promises does not exhaust available storage, because force will in
 59effect force such sequences iteratively.
 60
 61 (define (stream-filter p? s)
 62   (delay-force
 63    (if (null? (force s)) 
 64        (delay '())
 65        (let ((h (car (force s)))
 66              (t (cdr (force s))))
 67          (if (p? h)
 68              (delay (cons h (stream-filter p? t)))
 69              (stream-filter p? t))))))
 70 
 71 (head (tail (tail (stream-filter odd? integers)))) ==> 5 
 72
 73The following examples are not intended to
 74illustrate good programming style, as delay, force, and delay-force are mainly
 75intended for programs written in the functional style. However, they do
 76illustrate the property that only one value is computed for a promise, no
 77matter how many times it is forced.
 78
 79 (define count 0)
 80 (define p
 81   (delay (begin (set! count (+ count 1))
 82                 (if (> count x)
 83                     count
 84                     (force p)))))
 85 (define x 5)
 86 p                      ==>  a promise
 87 (force p)              ==>  6
 88 p                      ==>  a promise, still
 89 (begin (set! x 10)
 90        (force p))      ==>  6 
 91
 92Various extensions to this semantics of delay, 
 93force and delay-force are supported in some implementations:
 94
 95* Calling force on an object that is not a promise may simply return the object.
 96
 97* It may be the case that there is no means by which a promise can be
 98  operationally distinguished from its forced value. That is, expressions
 99  like the following may evaluate to either #t or to #f, depending on the
100  implementation:
101
102 (eqv? (delay 1) 1)           ==>  unspecified
103 (pair? (delay (cons 1 2)))   ==>  unspecified
104
105* Implementations may implement “implicit forcing,” where the value of a
106  promise is forced by procedures that operate only on arguments of a certain
107  type, like cdr and *. However, procedures that operate uniformly on their
108  arguments, like list, must not force them.
109
110 (+ (delay (* 3 7)) 13)   ==>  unspecified
111    (car
112    (list (delay (* 3 7)) 13))     ==> a promise
113
114<procedure>(promise? obj)</procedure>
115
116The promise? procedure returns #t if its argument is a promise, and #f
117otherwise. Note that promises are not necessarily disjoint from other Scheme
118types such as procedures.
119
120<procedure>(make-promise obj)</promise>
121
122The make-promise procedure returns a promise which, when forced, will return
123obj. It is similar to delay, but does not delay its argument: it is a procedure
124rather than syntax. If
125obj is already a promise, it is returned.
126
127---
128Previous: [[Module (scheme inexact)]]
129
130Next: [[Module (scheme load)]]